package zyj.yihong.leetcode.mid.graph;

import java.util.*;

/**
 * 934. 最短的桥
 * 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
 *
 * 现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
 *
 * 返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-bridge
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ShortestBridge934 {
    // 定义分类，岛屿1，标记为1，岛屿2，标记为2，0表示分隔
    int[][] classify;
    public int shortestBridge(int[][] grid) {
        classify = new int[grid.length][grid[0].length];
        boolean[][] visited = new boolean[grid.length][grid[0].length];

        // 通过dfs，处理classify
        dfs(grid);

        // 根据classify对source--target进行预处理
        Set<Integer> target = new HashSet<>();
        Queue<Node> sourceQueue = new ArrayDeque<>();

        for (int i = 0; i < classify.length; i++) {
            for (int j = 0; j < classify[0].length; j++) {
                if (classify[i][j]==1){
                    sourceQueue.add(new Node(i,j,0));
                    visited[i][j] = true;
                }else if (classify[i][j]==2){
                    target.add(i*classify[0].length+j);
                }
            }
        }

        // 对岛屿1中的每个node,进行bfs搜索
        while (!sourceQueue.isEmpty()){
            int size = sourceQueue.size();
            for (int i = 0; i < size; i++) {
                Node node = sourceQueue.poll();
                if (target.contains(node.i* grid[0].length+node.j)){
                    return node.step-1;
                }

                // 如果node不存在,则向四周找
                List<int[]> curNodeAround = getCurNodeAround(grid, node.i, node.j);
                for (int[] around : curNodeAround) {
                    // 如果是1则无需处理，当以这个1为起点的时候在计算最短距离
                    if (classify[around[0]][around[1]]!=1&&!visited[around[0]][around[1]]){
                        sourceQueue.add(new Node(around[0],around[1], node.step+1));
                        visited[around[0]][around[1]] = true;
                    }
                }
            }
        }
        return -1;
    }

    private void dfs(int[][] grid){
        int num = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 当出现第一个不为0是，视为第一个岛屿，然后根据此时的i，j
                // 进行dfs标记所有的岛屿1的位置
                if (grid[i][j]==1&&classify[i][j]==0){
                    Stack<Integer> stack = new Stack<>();
                    stack.add(i*grid[0].length+j);
                    num++;
                    classify[i][j] = num;
                    while (!stack.isEmpty()){
                        // 向周围寻找是否存在连续的1
                        Integer pop = stack.pop();
                        List<int[]> curNodeAround = getCurNodeAround(grid, pop/grid[0].length, pop%grid[0].length);
                        for (int[] node : curNodeAround) {
                            // 1添加到栈中，下次继续深度
                            if (grid[node[0]][node[1]]==1&&classify[node[0]][node[1]]==0){
                                classify[node[0]][node[1]] = num;
                                stack.push(node[0]*grid[0].length+node[1]);
                            }
                        }
                    }
                }
            }
        }
    }




    // 给定ij，获取i,j有效的上下左右范围
    private List<int[]> getCurNodeAround(int[][] grid,int i,int j){
        List<int[]> ans = new ArrayList<>();
        int m = grid.length;
        int n = grid[0].length;
        if (i+1<m){
            int[] ints = {i+1,j};
            ans.add(ints);
        }

        if (i-1>=0){
            int[] ints = {i-1,j};
            ans.add(ints);
        }

        if (j+1<n){
            int[] ints = {i,j+1};
            ans.add(ints);
        }

        if (j-1>=0){
            int[] ints = {i,j-1};
            ans.add(ints);
        }

        return ans;
    }

    // 为grid中的每一个点定义一个node,其中step用与广度查找时，当前所走的步
    // 如果当前这一步到达了另一个岛屿中，那么结果走了step-1;
    static class Node{
        int i;
        int j;
        int step;

        public Node(int i, int j, int step) {
            this.i = i;
            this.j = j;
            this.step = step;
        }
    }

    public static void main(String[] args) {
        ShortestBridge934 shortestBridge934 = new ShortestBridge934();
        int[][] grid = {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,0,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
        int i = shortestBridge934.shortestBridge(grid);
        System.out.println(i);
    }
}
